class Solution {
public:
    int maximumCandies(vector<int>& candies, long long k) {
        int left = 1, right =  *max_element(candies.begin(),candies.end());
        auto fun = [&](int num) -> bool {
            if(num == 0) return 0;
            long long people = 0;
            for (int cand : candies) {
                people += cand / num;
                if (people >= k) {
                    return true;
                }
            }
            return false;
        };
        while (left <= right) {
            int mid = (left + right) / 2;
            if (fun(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
            // cout << left <<' ' << right << endl;
        }
        // if(right == 0) return 0;
        return right;
    }
};
class Solution {
public:
    int maximumLength(string s) {
        vector<vector<int>> vvi(26);
        int n = s.size();
        for (int left = 0, right = 0; right <= n; right++) {
            if (right == n || s[left] != s[right]) {
                vvi[s[left] - 'a'].push_back(right - left);
                left = right;
            }
        }
        int ans = 0;
        for (int i = 0; i < 26; i++) {
            if (vvi[i].empty())
                continue;
            sort(vvi[i].begin(), vvi[i].end(), greater());
            vvi[i].push_back(0);
            vvi[i].push_back(0);
            int ans1 = vvi[i][0] - 2;
            int ans2 = min(vvi[i][0] - 1, vvi[i][1]);
            int ans3 = vvi[i][2];
            ans = max({ans, ans1, ans2, ans3});
        }
        if(ans == 0) return -1;
        return ans;
    }
};
class Solution {
public:
    int maxNumOfMarkedIndices(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size(),left = 0,right = n/2;
        auto fun = [&](int mid){
            int tmp = 0;
            // 0 ---- n - 1 -----1
            // 0 ---- n - 2 -----2
            // 1 ---- n - 1 -----2
            // 2 3 4 5
            while(tmp < mid){
                if(2* nums[tmp] > nums[n - mid + tmp]){
                    return false;
                }
                tmp++;
            }
            return true;
        };
        while(left <= right){
            int mid = (left + right) /2;
            // cout << left <<' ' << right << endl;
            if(fun(mid)){
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }
        return right*2;
    }
};
class Solution {
public:
    int maximumRemovals(string s, string p, vector<int>& removable) {
        int left = 0, right = removable.size(), n = right;
        int n1 = s.size(), n2 = p.size();
        auto fun = [&](int mid) {
            string tmp = s;
            for (int i = 0; i < mid; i++)
                tmp[removable[i]] = '1';
            int a1 = 0, a2 = 0;
            while (a1 < n1 && a2 < n2) {
                if (tmp[a1] == p[a2]) {
                    a1++, a2++;
                    if (a2 == n2)
                        return true;
                } else {
                    a1++;
                }
            }
            return false;
        };
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (fun(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};
using ll = long long;
class Solution {
public:
// 2 1 0 0         4 3 5
// 6 1 10
// 2 3 2 1 0
    int maxValue(int n, int index, int maxSum) {
        if(maxSum < n) return 0;
        int left = 1,right = maxSum;
        auto fun = [&](int mid) -> bool{
            ll tmp = 0,l = 0,r = 0;
            tmp = min(index ,mid - 1);
            l += max(index - mid + 1,0);
            l += (2*mid - tmp - 1) * tmp /2;
            tmp = min(mid, n - index);
            r += max(n - index - mid,0);
            r += (2 *mid - tmp + 1) * tmp/2;
            return r + l <= maxSum; 
        };
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (fun(mid)) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }
};

class Solution {
public:
    int furthestBuilding(vector<int> heights, int bricks, int ladders) {
        int n = heights.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        int sum = 0;
        for(int pos = 1;pos < n;pos++){
            if(heights[pos] > heights[pos - 1]){
                // 往高了走
                int a = heights[pos] - heights[pos - 1];
                pq.push(a); // 优先走梯子
                if(pq.size() > ladders){
                    sum += pq.top();    //   小的走台阶
                    pq.pop();
                }
                if(sum > bricks){
                    return pos - 1;
                }
            }
        }
        return n - 1;
    }
};
class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget,
                          vector<vector<int>>& composition, vector<int>& stock,
                          vector<int>& cost) {
        int ans = 0, i = 0;
        auto fun = [&](long long mid) {
            auto& vv = composition[i];
            long long tack = 0;
            for (int j = 0; j < n; j++) {
                tack += max((long long)0,mid * vv[j] - stock[j]) * cost[j];
                if(tack > budget){
                    return false;
                }
            }
            return true;
        };
         for (i = 0; i < k; i++) {
            long long left = 0, right = 10000000000;
            while (left <= right) {
                long long mid = (left + right) >> 1;
                if (fun(mid)) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // cout << right << endl;
            ans = max(ans, (int)right);
        }
        return ans;
    }
};